package primary.code06_graph;

import java.util.*;

/**
 * 最小生成数算法，prim算法
 *
 * 用权值总计最小的边连通所有节点
 *
 * 思路：
 * 从任一节点开始
 * 当前所能访问边的最小堆
 * 当前已经连通的点集合
 * 初始化 边集结果
 * while 能访问边的最小堆不为空
 *      弹出可访问的最小边
 *      检查通过该边是否能发现新节点
 *      能则更新边集结果、连通的点集合、所能访问边的最小堆；否则丢弃
 * end
 */
public class Code06_Prim {

    /**
     * 从点的角度出发
     * 每次获取最小的边，假如不构成环则加入结果中
     *
     * @param g
     * @return
     */
    public static List<Edge> prim(Graph g) {
        List<Edge> res = new ArrayList<>();
        //存储群落可以延伸的边集
        final PriorityQueue<Edge> edges = new PriorityQueue<>();
        //存储群落中的点集
        final HashSet<Node> nodes = new HashSet<>();
        for (Node node : g.nodes.values()) {
            if (!nodes.contains(node)) {
                //初始化
                nodes.add(node);
                edges.addAll(node.edges);
                while (!edges.isEmpty()) {
                    Edge e = edges.poll();
                    Node to = e.to;
                    //该最小边可以吸纳新节点
                    if (!nodes.contains(to)) {
                        res.add(e);
                        edges.addAll(to.edges);
                        nodes.add(to);
                    }
                }
            }
        }
        return res;
    }

    public static List<Edge> primTest(Graph g) {
        if (g == null || g.nodes == null || g.nodes.isEmpty()) return Collections.emptyList();
        List<Edge> res = new ArrayList<>();
        Set<Node> visitedNodes = new HashSet<>();
        for (Node node : g.nodes.values()) {
            if (visitedNodes.contains(node)) continue;
            PriorityQueue<Edge> visitableEdges = new PriorityQueue<>();
            visitedNodes.add(node);
            visitableEdges.addAll(node.edges);
            while (!visitableEdges.isEmpty()) {
                Edge curEdge = visitableEdges.poll();
                if (!visitedNodes.contains(curEdge.to)) {
                    res.add(curEdge);
                    visitedNodes.add(curEdge.to);
                    visitableEdges.addAll(curEdge.to.edges);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] arr = {
                {25, 1, 2},
                {25, 2, 1},

                {2, 1, 3},
                {2, 3, 1},

                {7, 1, 4},
                {7, 4, 1},

                {16, 2, 3},
                {16, 3, 2},

                {20, 2, 4},
                {20, 4, 2},

                {11, 4, 3},
                {11, 3, 4}
        };
        Graph graph = GraphUtils.transferGraph(arr);
        List<Edge> list1 = prim(graph);
        List<Edge> list2 = primTest(graph);

        for (Edge e : list1) {
            System.out.print("   " + e.weight);
        }
        System.out.println("\n======");
        for (Edge e : list2) {
            System.out.print("   " + e.weight);
        }
    }
}
